//
// Created by Administrator on 2021/4/7.
//
#include <iostream>

using namespace std;

//  Definition for a binary tree node.
// 树节点定义
struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool check(TreeNode *t, int target) {
        if (t == nullptr) return false; // 空节点
        else if (t->left == nullptr and t->right == nullptr) { // 叶节点
            return t->val == target;
        } else { // 非叶节点
            return check(t->left, target - t->val) or check(t->right, target - t->val);
        }
    }

    bool hasPathSum(TreeNode *root, int targetSum) {
        // 计算每一条到叶节点的路径之和是否为targetSum
        // 从当前节点到叶节点的和是否为targetSum - 当前值
        if (check(root, targetSum)) return true;
        else return false;
    }
    // AC
};
#include <queue>
class Solution2 {  // 题解 迭代 bfs
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        queue<TreeNode *> que_node;
        queue<int> que_val;
        que_node.push(root);
        que_val.push(root->val);
        while (!que_node.empty()) {
            TreeNode *now = que_node.front();
            int temp = que_val.front();
            que_node.pop();
            que_val.pop();
            if (now->left == nullptr && now->right == nullptr) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now->left != nullptr) {
                que_node.push(now->left);
                que_val.push(now->left->val + temp);
            }
            if (now->right != nullptr) {
                que_node.push(now->right);
                que_val.push(now->right->val + temp);
            }
        }
        return false;
    }
};

int main() {
    auto t9 = TreeNode(1);
    auto t8 = TreeNode(2);
    auto t7 = TreeNode(7);
    auto t6 = TreeNode(4, nullptr, &t9);
    auto t5 = TreeNode(13);
    auto t4 = TreeNode(11, &t7, &t8);
    auto t3 = TreeNode(8, &t5, &t6);
    auto t2 = TreeNode(4, &t4, nullptr);
    auto t1 = TreeNode(5, &t2, &t3);
    Solution sol;
    cout << sol.hasPathSum(&t1, 22);
//    auto t3 = TreeNode(3);
//    auto t2 = TreeNode(2);
//    auto t1 = TreeNode(1, &t2, &t3);
//    Solution sol;
//    cout << sol.hasPathSum(&t1, 4);
    return 0;
}